// Created by WXX on 2021/12/25 20:20
#include "MyTree.h"

/**
 * 执行用时：204 ms, 在所有 C++ 提交中击败了98.30%的用户
 * 内存消耗：147.1 MB, 在所有 C++ 提交中击败了88.51%的用户
 */
class Solution {
public:
    bool isEvenOddTree(TreeNode* root) {

        int level = 0;
        queue<TreeNode*> q;
        q.push(root);
        while (q.size()) {
            int n = q.size();
            int last = 0;
            if (level % 2) last = 1e7;

            while (n--) {
                auto t = q.front();
                q.pop();
                if (level % 2 == 0) {
                    if (t->val % 2 == 0) return false;
                    if (last >= t->val) return false;
                } else {
                    if (t->val % 2 == 1) return false;
                    if (last <= t->val) return false;
                }

                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
                last = t->val;
            }
            level++;
        }
        return true;
    }
};

int main() {

    int nu = INT_MAX;
    vector<int> nums = {
            1,
            10, 4,
            3, nu, 7, 9,
            12, 8, nu, nu, 6, nu, nu, 2
    };
    TreeNode *root = MyTree(nums).getRoot();
    cout << Solution().isEvenOddTree(root) << endl;

    return 0;
}
